`:top

`!Tree-adjoining grammar`!s (TAG), auch `!Baumadjunktions-Grammatiken`!, sind `F33f`_`[formale Grammatiken`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Formale_Grammatik]`_`f, die von `F33f`_`[Aravind Joshi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Aravind_Joshi]`_`f eingeführt wurden`:cite-ref-0-1-0[`F5bf`_`[1`#cite-note-0-1]`_`f] und in der `F33f`_`[Computerlinguistik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Computerlinguistik]`_`f für die Beschreibung von `F33f`_`[natürlichen Sprachen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Natürliche_Sprache]`_`f verwendet werden.

TAGs ähneln `F33f`_`[kontextfreien Grammatiken`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextfreie_Grammatik]`_`f, verwenden aber `F33f`_`[Bäume`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Baum_(Graphentheorie)]`_`f statt Symbole als kleinste Elemente. Diese `*Elementarbäume`* werden nach festgelegten Regeln, `*Substitution`* und `*Adjunktion`*, miteinander zu immer größeren Bäumen kombiniert. Am Ende des Prozesses kann an den Blättern des entstandenen Baumes ein Satz als Folge von Worten abgelesen werden. Die Menge der durch eine konkrete Baumadjunktionsgrammatik beschreibbaren Sätze bildet die Sprache dieser TAG.

TAGs werden als schwach kontextsensitiv (`*mildly context-sensitive`*) beschrieben; sie sind also stärker als kontextfreie Grammatiken, aber schwächer als `F33f`_`[kontextsensitive Grammatiken`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextsensitive_Grammatik]`_`f in der `F33f`_`[Chomsky-Hierarchie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chomsky-Hierarchie]`_`f.`:cite-ref-1-2-0[`F5bf`_`[2`#cite-note-1-2]`_`f] Daher sind sie vermutlich stark genug, um natürliche Sprachen zu erzeugen, aber auch schwach genug, um noch effizient `F33f`_`[parsebar`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Parser]`_`f zu sein.

>>Contents

• `F0af`_`[Einstiegsbeispiel`#einstiegsbeispiel]`_`f

• `F0af`_`[Definition`#definition]`_`f

• `F0af`_`[Expressivität`#expressivit-t]`_`f

• `F0af`_`[Relation zu kontextfreien Grammatiken`#relation-zu-kontextfreien-grammatiken]`_`f

• `F0af`_`[Schwach kontextsensitive Sprachen`#schwach-kontextsensitive-sprachen]`_`f

• `F0af`_`[Parsing`#parsing]`_`f

• `F0af`_`[Varianten und Erweiterungen`#varianten-und-erweiterungen]`_`f

• `F0af`_`[Siehe auch`#siehe-auch]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Weblinks`#weblinks]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Einstiegsbeispiel

Eine Baumadjunktionsgrammatik, die sowohl den Satz `*Rumo schnarcht`* als auch `*Rumo schnarcht nie`* verarbeiten kann, lässt sich zum Beispiel mit drei Elementarbäumen darstellen:

• ein `!Initalbaum`! α α 1 {\\displaystyle \\alpha _{1}} für die `F33f`_`[Nominalphrase`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nominalphrase]`_`f für das Wort `*Rumo`*. Der Baum besteht aus dem Symbol NP (einem `F33f`_`[Nichtterminalsymbol`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nichtterminalsymbol]`_`f), welches zu dem Wort `*Rumo`* (einem `F33f`_`[Terminalsymbol`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Terminalsymbol]`_`f) expandiert.

• ein `!Initalbaum`! α α 2 {\\displaystyle \\alpha _{2}} für das Verb `*schnarcht`*. Der Baum zeigt an, dass dem Verb zu einem ganzen Satz noch eine Nominalphrase (NP) fehlt. Der Baumknoten NP ist mit ↓ ↓ {\\displaystyle \\downarrow } als `*Substitutionsknoten`* markiert, um zu signalisieren, dass an dieser Stelle noch ein Baum mit einer NP als Wurzel eingesetzt werden muss. Ansonsten besteht der α α 2 {\\displaystyle \\alpha _{2}} -Baum noch aus einer `F33f`_`[Verbalphrase`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Verbalphrase]`_`f (VP), welche wiederum aber lediglich aus dem Verb `*schnarcht`* besteht.

• ein `!Auxiliarbaum`! β β 1 {\\displaystyle \\beta _{1}} für das Adverb `*nie`*. Der Baum besteht neben dem `F33f`_`[Adverb`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Adverb]`_`f `*nie`* noch aus zwei weiteren VP-Knoten. Jeder Auxiliarbaum besitzt einen speziellen Fußknoten, markiert durch ∗ ∗ {\\displaystyle \\ast } , der das gleiche Nichtterminal wie die Wurzel des Baums aufweisen muss. In diesem Fall ist das eine VP. Dieser Baum kann also dazu genutzt werden, um Verbalphrasen zu modifizieren.

Um den Satz `*Rumo schnarcht`* zu erhalten, müssen nur die zwei Initialbäume α α 1 {\\displaystyle \\alpha _{1}} und α α 2 {\\displaystyle \\alpha _{2}} mittels `*Substitution`* miteinander kombiniert werden. Dazu wird der Substitutionsknoten mit der Wurzel des NP-Baums ersetzt. Soll der Satz um das Adverb `*nie`* erweitert werden, kommt die Adjunktion zum Einsatz, die den Baumadjunktionsgrammatiken auch ihren Namen gab. Bei der Adjunktion wird der Baum des bisherigen Satzes am VP-Knoten quasi in zwei Teile gerissen. Der Teilbaum des Satzes oberhalb des ursprünglichen VP-Knotens endet nun in der Wurzel des Auxiliarbaums β β 1 {\\displaystyle \\beta _{1}} , während der unter Teilbaum nun an dem ehemaligen Fußknoten des Auxiliarbaums beginnt. Theoretisch kann diese Adjunktion beliebig oft wiederholt werden (`*Rumo schnarcht nie nie nie nie ...`*).

>>Definition

Eine TAG ist ein 5-`F33f`_`[Tupel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Tupel]`_`f ( Σ Σ , N T , I , A , S ) {\\displaystyle (\\Sigma ,NT,I,A,S)} bestehend aus`:cite-ref-4-3-0[`F5bf`_`[3`#cite-note-4-3]`_`f]

• Σ Σ {\\displaystyle \\Sigma } , einer endlichen Menge von `F33f`_`[Terminalsymbolen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Terminalsymbol]`_`f;

• N T {\\displaystyle NT} , einer endlichen Menge von `F33f`_`[Nichtterminalsymbolen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nichtterminalsymbol]`_`f, die mit der Menge der Terminale `F33f`_`[disjunkt`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Disjunkt]`_`f ist;

• I {\\displaystyle I} , einer endlichen Menge von `*Initialbäumen.`* Initialbäume sind solche Bäume, die

• als innere Knoten Nichtterminale besitzen und

• als Blätter Nichtterminale oder Terminale, wobei Nichtterminale mit ↓ ↓ {\\displaystyle \\downarrow } markiert sind, um Substitution anzuzeigen.

• A {\\displaystyle A} , einer endlichen Menge an `*Auxiliarbäumen`*. Auxiliarbäume sind solche Bäume, die

• als innere Knoten Nichtterminale besitzen und

• als Blätter Nichtterminale oder Terminale, wobei Nichtterminale üblicherweise mit ↓ ↓ {\\displaystyle \\downarrow } markiert werden, um Substitution anzuzeigen. Einer der Nichtterminalblätter ist hingegen nicht zur Substitution bestimmt, sondern ein `*Fußknoten`* (markiert als ∗ ∗ {\\displaystyle \\ast } ) mit dem gleichen Nichtterminal wie die Wurzel des Auxiliarbaums.

• S {\\displaystyle S} , dem speziellen Startsymbol der TAG, welches ein Nichtterminal ist: S ∈ ∈ N T {\\displaystyle S\\in NT}

Die Menge an Initial- und Auxiliarbäumen I ∪ ∪ A {\\displaystyle I\\cup A} wird Menge der `*Elementarbäume`* genannt.

Zur Kombination von Bäumen stehen zwei Operationen zur Verfügung: Substitution und Adjunktion:

• `*Substitution`*: bei dieser Operation wird ein Nichtterminalblatt eines Baumes durch die Wurzel eines anderen Baumes, der aus Initialbäumen abgeleitet wurde, ersetzt und damit die beiden Bäume verbunden.

• `*Adjunktion`*: bei dieser Operation wird ein Auxiliarbaum in einen anderen Baum eingefügt. Dieser zweite Baum muss dafür ein Nichtterminal besitzen, welches der Wurzel und dem Fußknoten des Auxiliarbaums entspricht. Adjunktion an für die Substitution markierten Blättern ist nicht erlaubt. Adjunktion sieht dabei wie folgt aus:

Daneben gibt es noch die Möglichkeit, `*Adjunktions-Constraints`* für Knoten einzuführen:`:cite-ref-4-3-1[`F5bf`_`[3`#cite-note-4-3]`_`f]

• `*Selektive Adjunktion`* (SA(T)): nur eine bestimmte Teilmenge T an Auxiliarbäumen darf an diesem Knoten adjungieren.

• `*Null Adjunktion`* (NA): an einem mit NA markierten Knoten darf nicht adjungiert werden.

• `*Obligatorische Adjunktion`* (OA(T)): an einem mit OA markierten Knoten muss adjungiert werden. Dazu muss ein Auxiliarbaum aus einer bestimmten Teilmenge T verwendet werden.

In der Definition von Joshi et al. (1975)`:cite-ref-0-1-1[`F5bf`_`[1`#cite-note-0-1]`_`f] gab es hingegen noch keine Constraints und Substitutionsknoten.`:cite-ref-4-3-2[`F5bf`_`[3`#cite-note-4-3]`_`f]

>>Expressivität

Obwohl TAGs aus Bäumen bestehen, fokussiert sich dieser Abschnitt auf die String-Sprachen von TAGs. Das sind die Sprachen, die sich an den Blättern der Bäume aus den Terminalsymbolen ablesen lassen.

>>>Relation zu kontextfreien Grammatiken

Zu jeder `F33f`_`[kontextfreien Grammatik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextfreie_Grammatik]`_`f (CFG, für englisch `*context-free grammar`*) kann eine TAG erzeugt werden, die die gleiche String-Sprache akzeptiert. Damit können TAGs alle `F33f`_`[kontextfreien Sprachen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextfreie_Sprache]`_`f beschreiben.`:cite-ref-0-1-2[`F5bf`_`[1`#cite-note-0-1]`_`f]

>>>Schwach kontextsensitive Sprachen

TAGs können aber mehr Sprachen beschreiben als kontextfreie Grammatiken. Denn mit TAGs können auch einige, aber nicht alle `F33f`_`[kontextsensitiven Sprachen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextsensitive_Sprache]`_`f beschrieben werden, wie folgende Beispiele verdeutlichen.

Zu den Beispielen von kontextsensitiven Sprachen, die von TAGs akzeptiert werden können, zählen folgende:

• Die Copy-Sprache COPY = { w w ∣ ∣ w ∈ ∈ Σ Σ ∗ ∗ } {\\displaystyle {\\textsf {COPY}}=\\left\\{ww\\mid w\\in \\Sigma ^{*}\\right\\}} kann von TAGs mit Adjunktionsconstraints ausgedrückt werden.`:cite-ref-2-4-0[`F5bf`_`[4`#cite-note-2-4]`_`f]`:cite-ref-3-5-0[`F5bf`_`[5`#cite-note-3-5]`_`f] Wenn das Vokabular Σ Σ = { a , b } {\\displaystyle \\Sigma =\\left\\{a,b\\right\\}} ist, reichen nur drei Bäume aus, um die Sprache zu beschreiben. Ein Baum für das `F33f`_`[leere Wort`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Leeres_Wort]`_`f und je ein weiterer für das Symbol `*a`* und `*b`*. Zur Sprache gehören Sätze wie `*abab`* und `*abaaba`*.

• Die Count-4-Sprache,`:cite-ref-3-5-1[`F5bf`_`[5`#cite-note-3-5]`_`f] bei der genau gleich viele Symbole `*a`*, `*b`*, `*c`* und `*d`* generiert werden sollen, kann auch von TAGs mit Adjunktionsconstraints beschrieben werden. Formal ist diese definiert als COUNT 4 = { a n b n c n d n ∣ ∣ n ≥ ≥ 0 } {\\displaystyle {\\textsf {COUNT}}_{4}=\\left\\{a^{n}b^{n}c^{n}d^{n}\\mid n\\geq 0\\right\\}} und lässt sich mit nur zwei Bäumen generieren.`:cite-ref-3-5-2[`F5bf`_`[5`#cite-note-3-5]`_`f]

Zwei Beispiele für kontextsensitive Sprachen, die TAGs nicht beschreiben können, sind die Count-5-Sprache COUNT 5 = { a n b n c n d n f n ∣ ∣ n ≥ ≥ 0 } {\\displaystyle {\\textsf {COUNT}}_{5}=\\left\\{a^{n}b^{n}c^{n}d^{n}f^{n}\\mid n\\geq 0\\right\\}} und die doppelte Copy-Sprache DOUBLE-COPY = { w w w ∣ ∣ w ∈ ∈ Σ Σ ∗ ∗ } {\\displaystyle {\\textsf {DOUBLE-COPY}}=\\left\\{www\\mid w\\in \\Sigma ^{*}\\right\\}} .`:cite-ref-3-5-3[`F5bf`_`[5`#cite-note-3-5]`_`f]

TAGs können die gleichen `*schwach kontextsensitiven`* Sprachen von Strings wie zum Beispiel kombinatorische Kategorialgrammatiken (`*Combinatory Categorical Grammars`*, CCGs) erzeugen.`:cite-ref-1-2-1[`F5bf`_`[2`#cite-note-1-2]`_`f]

>>>Parsing

TAGs können mit einem `F33f`_`[CYK`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cocke-Younger-Kasami-Algorithmus]`_`f- oder `F33f`_`[Early`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Earley-Algorithmus]`_`f-ähnlichen`:cite-ref-2-4-1[`F5bf`_`[4`#cite-note-2-4]`_`f]`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f] Parsing-Algorithmus geparst werden. Sie sind daher noch in polynomieller Zeit, genauer in O ( n 6 ) {\\displaystyle {\\mathcal {O}}\\left(n^{6}\\right)} , parsebar (siehe `F33f`_`[Landau-Notation`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Landau-Notation]`_`f).`:cite-ref-4-3-3[`F5bf`_`[3`#cite-note-4-3]`_`f]

>>Varianten und Erweiterungen

• `!Lexikalisierte TAG (LTAG):`! bei einer LTAG enthält jeder Elementarbaum mindestens ein Terminalsymbol, welches auch (lexikalischer) Anker genannt wird.`:cite-ref-4-3-4[`F5bf`_`[3`#cite-note-4-3]`_`f]

• `!Feature-TAG (FTAG):`! Bäume werden mit Merkmalsstrukturen annotiert, um `F33f`_`[Kongruenz`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kongruenz_(Grammatik)]`_`f zu erzwingen, zum Beispiel zwischen einem Verb im `F33f`_`[Singular`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Singular]`_`f und dem Subjekt, das auch im Singular sein soll.`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]

>>Siehe auch

• `F33f`_`[Kontextfreie Grammatik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextfreie_Grammatik]`_`f

• `F33f`_`[Kontextsensitive Grammatik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kontextsensitive_Grammatik]`_`f

• `F33f`_`[Chomsky-Hierarchie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Chomsky-Hierarchie]`_`f

• `F33f`_`[Syntaxtheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Syntaxtheorie]`_`f

>>Literatur

• Stefan Müller: Grammatiktheorie. In: Stauffenburg Einführungen. Band 20. Stauffenberg Verlag, Tübingen 2010, ISBN 978-3-86057-805-6 (hu-berlin.de [PDF]). , insbesondere Kapitel 10 zu TAG.

• Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).

• Laura Kallmeyer: Parsing Beyond Context-Free Grammars (= Cognitive Technologies). Springer Berlin Heidelberg, Berlin, Heidelberg 2010, ISBN 978-3-642-14845-3, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1007/978-3-642-14846-0 (englisch, springer.com [abgerufen am 23. Juni 2025] Kapitel zu TAG auf Seiten 53 - 108).

• Aravind K. Joshi, Yves Shabes: Tree-Adjoining Grammars. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of Formal Languages. Springer, Berlin, Heidelberg 1997, ISBN 978-3-642-59126-6, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1007/978-3-642-59126-6_2.

>>Weblinks

• XTAG project, verwendet eine TAG für natürliche Sprache

• Seminar zu TAG von Laura Kallmeyer und Simon Petitjean für das Wintersemester 2015/16 mit Foliensätzen zu verschiedenen Bereichen von TAGs.

>>Einzelnachweise

`:cite-note-0-1`!1.`! `F0af`_`[↑`#cite-ref-0-1-0]`_`f Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).

`:cite-note-1-2`!2.`! `F0af`_`[↑`#cite-ref-1-2-0]`_`f David Jeremy Weir: Characterizing mildly context-sensitive grammar formalisms. University of Pennsylvania, United States Januar 1988 (englisch, acm.org – Dissertation in Computer and Information Science).

`:cite-note-4-3`!3.`! `F0af`_`[↑`#cite-ref-4-3-0]`_`f Aravind K. Joshi, Yves Schabes: Tree-Adjoining Grammars and Lexicalized Grammars. University of Pennsylvania Department of Computer and Information Science, 1. März 1991 (upenn.edu – Technical Report No. MS-CIS-91-22.).

`:cite-note-2-4`!4.`! `F0af`_`[↑`#cite-ref-2-4-0]`_`f K. Vijay-Shankar, Aravind K. Joshi: Some Computational Properties of Tree Adjoining Grammars. In: Strategic Computing - Natural Language Workshop: Proceedings of a Workshop Held at Marina del Rey, California, May 1-2, 1986. Mai 1986, S. 212–223 (englisch, aclanthology.org [PDF]).

`:cite-note-3-5`!5.`! `F0af`_`[↑`#cite-ref-3-5-0]`_`f Aravind K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: D. Dowty, L. Karttunen, and A. Zwicky (Hrsg.): Natural Language Parsing. Cambridge University Press, 1985, S. 206–250 (englisch, sfu.ca [PDF; abgerufen am 23. Juni 2025]).

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f Yves Schabes, Aravind K. Joshi: An Earley-Type Parsing Algorithm for Tree Adjoining Grammars. In: 6th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Buffalo, New York, USA Juni 1988, S. 258–269, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.3115/982023.982055 (englisch, aclanthology.org [PDF]).

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f K. Vijay-Shanker, A.K. Joshi: Feature Structures Based Tree Adjoining Grammars. In: Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics. 1988 (englisch, aclanthology.org [abgerufen am 26. Juni 2025]).

`c`F0af`_`[↑ Back to top`#top]`_`f`a